10700. Торговля верблюдами
В 800 году до нашей эры халиф
Багдада предоставил формулу 1+2*3*4+5 в финансовом отчете по торговле
верблюдами. Поскольку формула не содержала скобок, то она могла принимать
несколько значений в зависимости от порядка действий. Найдите минимально и
максимально возможное значение заданной формулы, которая может содержать лишь
числа и знаки сложения и умножения.
Вход. Первая строка содержит
количество тестов. Каждая следующая строка является отдельным тестом и содержит
выражение, состоящее из целых чисел, знаков сложения и умножения. Целых чисел
не более 12, их величины изменяются от 1 до 20.
Выход. Для каждого выражения вывести
его максимально и минимально возможные значения в соответствии с заданным в
примере форматом.
3
1+2*3*4+5
4*18+14+7*10
3+11+4*1*13*12*8+3*3+8
The maximum and minimum are 81 and 30.
The maximum and minimum are 1560 and
156.
The maximum and minimum are 339768 and
5023.
синтаксический анализ
Минимальное значение будет
принимать выражение, если сначала выполнить операции умножения, а потом –
сложения (умножение имеет приоритет над сложением). Максимальное значение
выражение примет, если сначала выполнить операции сложения, а потом – умножения
(сложение имеет больший приоритет над умножением). Остается записать грамматику
и вычислить выражение в каждом из двух случаев. Переменные First и Second типа
char будут содержать соответственно символы более и менее приоритетной
операции.
Грамматика для вычисления выражения,
в которой операция First имеет больший приоритет над операцией Second, имеет
вид:
S
®
S <операция Second > T | T
T ® T <операция First > F | F
F ® <число>
Преобразуем грамматику в не леворекурсивную
(e – пустое слово):
S ® TS1
S1 ® <операция
Second >TS1 | e
T ® FT1
T1 ® <операция
First >FT1 | e
F ® <число>
Для вычисления минимального
значения следует положить First = ‘*’, Second = ‘+’, для максимального First =
‘+’, Second = ‘*’.
Для первого теста минимальное
значение выражения будет достигаться, если расставить скобки следующим образом:
1 + (2 * 3 * 4) + 5 = 1 + 24 + 5 = 30. Максимальным будет выражение, если его вычислять
так: (1 + 2) * 3 * (4 + 5) = 3 *3 * 9 = 81.
Поскольку выражение имеет до 12
целых чисел от 1 до 20, то максимально возможным значением будет 2012,
что входит в 64-битовое целое. Объявим рабочие переменные a и b,
а также стек для интерпретации выражений:
long long
a, b;
stack<long
long> Stack;
Каждому нетерминальному символу
не леворекурсивной грамматики поставим в соответствие процедуру. Каждое правило
грамматики выпишем отдельной процедурой. Выпишем объявления процедур, так как
они взаимно вызывают друг друга.
void s1(void);
void t(void);
void t1(void);
void f(void);
void s(void)
{
t(); s1();
}
void s1(void)
{
if (c ==
Second)
{
t();
Для вычисления выражения здесь
следует взять два верхние значения со стека, произвести над ними операцию
Second и результат положить в стек.
a = Stack.top(); Stack.pop();
b = Stack.top(); Stack.pop();
if (Second
== '+') Stack.push(a+b); else Stack.push(a*b);
s1();
}
}
void t(void)
{
f(); t1();
}
void t1(void)
{
if (c ==
First)
{
f();
Производим операцию First над
двумя верхними значениями в стеке, результат кладем в стек.
a = Stack.top(); Stack.pop();
b = Stack.top(); Stack.pop();
if (First
== '*') Stack.push(a*b); else Stack.push(a+b);
t1();
}
}
void f(void)
{
int number;
Читаем очередное число number
и следующий за ним функциональный символ c. Если символа нет (конец
строки, функция sscanf вернет значение 1), то положим c = 0. Кладем
число в стек и увеличиваем указатель на количество прочитанных символов с
учетом того, что числа могут быть или однозначными или двузначными.
if
(sscanf(stroka+ptr,"%d%c",&number,&c)
!= 2) c = 0;
Stack.push(number);
if (number
< 10) ptr += 2; else ptr += 3;
}
В функции main программы читаем
количество тестов tests. Выражение читаем в строку stroka, текущий указатель
разбора выражения ptr устанавливаем в 0. В переменную first
занесем знак операции, который имеет приоритет над знаком, занесенным в
переменную second. После вычисления выражения (вызова функции s)
результат находится на вершине стека. Заносим результаты в переменные opt1,
opt2 типа long long и печатаем их. После первого вычисления выражения
следует очистить стек и установить указатель ptr на начало выражения.
scanf("%d",&tests);
while(tests--)
{
scanf("%s",&stroka);
ptr = 0;
First = '+';
Second = '*'; s(); opt1 = Stack.top();
Stack.pop(); ptr = 0;
First = '*';
Second = '+'; s(); opt2 = Stack.top();
printf("The
maximum and minimum are %lld and %lld.\n",opt1,opt2);
}